package chapter_04;


// 优先级队列
/*
insert()方法先检查队列中是否有数据项；如果没有，就插入到下标为0的单元里。否则，
从数组顶部开始向上移存在的数据项，直到找到新数据项应当插入的位置。然后，插入新
数据项，并把nItems加1。注意优先级队列可能会出现满的情况，应当在用insert()方法
之前先用isFull()判断这种可能性。

优先级队列的效率
插入操作需要O(N)的时间，而删除操作则需要O(1)的时间。

在数据项个数比较少，或不太关心速度的情况下，用数组实现优先级队列还可以满足要求。
如果数据项很多时，或速度很重要时，采用堆是更好的选择。
 */

public class PriorityQ {
    private int maxSize;
    private long[] queArray;
    private int nItems;

    public PriorityQ(int s) {
        maxSize = s;
        queArray = new long[maxSize];
        nItems = 0;
    }

    public void insert(long item) {
        int j;

        if (0 == nItems)
            queArray[nItems++] = item;
        else {
            for (j = nItems - 1; j >= 0; j--) {
                // 将比item小的值向后移
                if (item > queArray[j])
                    queArray[j + 1] = queArray[j];
                else
                    break;
            }
            queArray[j + 1] = item;
            nItems++;
        }
    }

    public long remove() {
        return queArray[--nItems];
    }

    public long peekMin() {
        return queArray[nItems - 1];
    }

    public boolean isEmpty() {
        return  0 == nItems;
    }

    public boolean isFull() {
        return nItems == maxSize;
    }

    public static void main(String[] args) {
        PriorityQ thePQ = new PriorityQ(5);
        thePQ.insert(30);
        thePQ.insert(50);
        thePQ.insert(10);
        thePQ.insert(40);
        thePQ.insert(20);

        while (!thePQ.isEmpty()) {
            long item = thePQ.remove();
            System.out.print(item + " ");
        }
        System.out.println();
    }
}
